package nachos.threads;

import nachos.machine.*;
import nachos.threads.PriorityScheduler.ThreadState;

import java.util.Comparator;
import java.util.TreeSet;
import java.util.HashSet;
import java.util.Iterator;

/**
 * A scheduler that chooses threads using a lottery.
 *
 * <p>
 * A lottery scheduler associates a number of tickets with each thread. When a
 * thread needs to be dequeued, a random lottery is held, among all the tickets
 * of all the threads waiting to be dequeued. The thread that holds the winning
 * ticket is chosen.
 *
 * <p>
 * Note that a lottery scheduler must be able to handle a lot of tickets
 * (sometimes billions), so it is not acceptable to maintain state for every
 * ticket.
 *
 * <p>
 * A lottery scheduler must partially solve the priority inversion problem; in
 * particular, tickets must be transferred through locks, and through joins.
 * Unlike a priority scheduler, these tickets add (as opposed to just taking
 * the maximum).
 */
public class LotteryScheduler extends PriorityScheduler {
    /**
     * Allocate a new lottery scheduler.
     */
    public LotteryScheduler() {
    }
    
    /**
     * Allocate a new lottery thread queue.
     *
     * @param	transferPriority	<tt>true</tt> if this queue should
     *					transfer tickets from waiting threads
     *					to the owning thread.
     * @return	a new lottery thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {
	// implement me
    	if(transferPriority)
    	{
    		return new LotteryQueue(transferPriority);
    	}
    	else
    	{
    		return new PriorityQueue(transferPriority);
    	}
	//return null;
    }
    
    
    @Override
	protected ThreadState getThreadState(KThread thread) {
		// TODO Auto-generated method stub
		if (thread.schedulingState == null)
			thread.schedulingState = new LotteryState(thread);
		return (ThreadState) thread.schedulingState;
	}


	protected class LotteryState extends ThreadState
    {

		public LotteryState(KThread thread) {
			super(thread);
		}
    	public int getEffectivePriority()
    	{
    		int ep = this.priority;
    		ThreadQueue que = this.thread.getWaitQueue();
    		if(que instanceof PriorityQueue)
    		{
    			PriorityQueue q = (PriorityQueue) que;
    			java.util.PriorityQueue<ThreadState> pque = q.que;
    			ThreadState[] array = new ThreadState[pque.size()];
    			pque.toArray(array);
    			for(ThreadState ts :array)
    			{
    				ep+=ts.getEffectivePriority();
    			}
    		}
    		return ep;
    	}
    }
    protected class LotteryQueue extends PriorityQueue
    {
    	 LotteryQueue(boolean transfer)
    	{
    		 super();
    		 this.transferPriority = transfer;
    		 this.cmp=new Comparator<ThreadState>() {
 				@Override
 				public int compare(ThreadState c1, ThreadState c2) {
 					if (c1.getEffectivePriority() != c2.getEffectivePriority())
 						return (int) (c1.getEffectivePriority() - c2.getEffectivePriority());
 					else
 						return (int) (c1.getTime() - c2.getTime());
 				}
 			};
 			que = new java.util.PriorityQueue<ThreadState>(Integer.MAX_VALUE, cmp);
    	}
    	 
    	 
    	 
    }
}
